This invention relates to transmission of information between two or more digital devices. More particularly, this invention relates to a method and apparatus for avoiding packet loss in a CSMA/CD (Carrier Sense Multiple Access with Collision Detection) network.
Local area networks (LANs) are arrangements of various hardware and software elements that operate together to allow a number of digital devices to exchange data. In the context of network communication, devices on a network are variously referred to as "stations," "nodes," "end systems" (ES), or "data terminal equipment" (DTE). LANs typically are optimized for use in a limited geographic region such as a single office building or a campus.
LANs may vary in the topology of the interconnections among devices. In the context of a communication network, the term "topology" refers to the way in which the stations attached to the network are interconnected. The common topologies for LANs are bus, tree, ring, and star. LANs may also have a hybrid topology made up of a mixture of these.
A number of standards have been adopted in the communication industry for various types of LANs. These standards specify and standardized aspects of the physical (hardware) configuration of network equipment as well as the algorithms (software) used to control network data exchange. Much of the work on the development of LAN standards has been done through the IEEE by a committee known as IEEE 802. The committee has issued a set of four LAN standards: a CSMA/CD standard (IEEE 802.3), a token bus standard (IEEE 802.4), a token ring standard (IEEE 802.5), and an FDDI (Fiber-Distributed Data Interface) standard (IEEE FDDI). These standards subsequently have been revised and reissued by the ISO (International Organization For Standardization) with the designation ISO 8802.
In developing the 802 standards, the IEEE came to the conclusion that the task of communication across the LAN was sufficiently complex that it needs to be broken up into more manageable subtasks. As a result, the 802 standards have organized the tasks of network communication into "layers." The IEEE 802 committee specified three layers for each of the 802 standards, the Physical Layer, Media-access control layer, and Logical Link Control (LLC) layer. These layers are a subset of the well-known Open Systems Interconnection (OSI) layered communication architecture. The OSI layered architecture defines seven layers: physical, data link, network, transport, session, presentation and application.
The 802 Physical Layer handles the encoding/decoding of physical transmission signals, the generation/removal of preambles for transmitted data used for synchronization, and the bit transmission/reception protocol. At the Physical Layer, data is treated as an unformatted bit stream transmitted from one transmitter to one or more receivers over a single link. The 802 Physical Layer specification includes specification of the transmission medium.
The 802 Media-access Control Layer handles data as a series of independent packets, each packet containing its own destination address and fields specifying packet length, priority, and codes for error checking.
The 802 Logical-Link Control (LLC) Layer handles higher-level functions of data exchange between two stations on a network. The LLC specifies three forms of service to LLC users: an unacknowledged connectionless service, a connection-mode service, and an acknowledged connectionless service. In the unacknowledged connectionless service mode a user will make a request at the LLC layer to send a unit of data to a receiver and the LLC will handle transmission by interfacing with the lower layers, but the user will never receive an acknowledgement back from the receiver. In the connection-mode service, the LLC layer or a transmitter will make a semi-permanent connection with the LLC layer of a receiver to facilitate the sending of a stream of packets.
Each of the 802 standards includes specifications at each of the three layers. However, the standards do not necessarily specify the LAN topology, and the same protocol may operate on different network topologies. The 802.3 standard, for example, may operate on a bus, star or hybrid topology.
IEEE Standard 802.3 defines a LAN that uses at its Media-access Control layer a CSMA/CD protocol. This standard was based on the older Ethernet network protocol and 802.3 networks are often referred to as Ethernet networks. As originally conceived and implemented, an Ethernet network allowed a number of stations to each be directly connected to a single communication medium in a bus topology. As an example of the original Ethernet configuration, FIG. 1 depicts a LAN 10 having four stations 12 connected to a physical communication channel 14 in a bus topology. Although the depicted stations 12 are shown as personal computer workstations, a station typically may be any digital device such as a computer device, a peripheral device, or a digital telephone. The workstations 12 are connected to the communication channel 14 through adapters 13. The adapters 13 are specialized circuits that handle transmissions on the network. The communication channel 14 may be an unshielded twisted pair wire (UTP), a shielded twisted pair wire, a coaxial cable or another medium capable of carrying a digital signal. Unshielded twisted pair wire is the conventional wiring in buildings for telephone systems, and thus, is a convenient communication channel.
In a CSMA/CD LAN, peer-to-peer communications among stations are supported without the intervention of a central controller for the network. At the Media-access Control layer, in order to access the network under the CSMA/CD standard, an adaptor 13 connected to a station 12 first listens to the communication channel to determine whether or not another station is transmitting (the carrier sense). If no carrier is sensed, then the adaptor 13 transmits a packet of data on the communication channel 14.
Occasionally, two or more station adapters will listen to the channel at or near the same time, will not sense a carrier, and then will transmit at the same time, resulting in a garbled transmission referred to as a "collision." A receiving station adaptor ignores the garbled transmission, while a transmitting station adaptor must detect the collision and cease transmission once it detects the collision. After a collision, each transmitting adaptor that detected the collision waits a period of time, known as "back-off" time, before attempting to retransmit. The back-off time is measured in a discrete unit defined by a network parameter known as the "slot time." To reduce the chances of a repeated collision, each adaptor generates a random integer which determines the number of slot times that it will wait for back-off. In standard Ethernet, this integer is determined by an algorithm known as "truncated binary exponential backoff." The truncated binary exponential backoff algorithm takes into account the fact that when traffic on the Ethernet channel is heavy, a transmitting station may make a number of unsuccessful attempts to transmit a particular packet. According to the algorithm, the maximum possible backoff is doubled each time an attempt is made to transmit a particular packet. On the first attempt after a collision, the random integer picked by each transmitting station that detected a collision is either 0 or 1, on the second attempt it is between 0 and 3 inclusive, on the third attempt it is between 0 and 7, and so on. Once the backoff time has elapsed, a transmitter listens for a carrier and transmits as soon as there is no carrier on the channel.
Standard 802.3 Ethernet adapters are programmed to make a finite number of attempts (referred to as the maximum attempt limit) to transmit a particular packet before discarding that packet and alerting their station that the packet has been discarded. For standard 802.3 Ethernet, the predetermined maximum attempt limit is sixteen.
The preceding described actions of the CSMA/CD protocol are handled by the Media-access Control layer of the protocol. At the Media-access Control layer, the station only knows whether a data packet was transmitted with no collision detected or whether a collision was detected during transmission. At the LLC layer of the protocol, the receiving station checks the received data packet for validity and then, in acknowledged-connectionless mode or in connection-mode, the receiver sends a acknowledgement packet or a retransmit request back to the transmitting station to let the transmitting station know whether the packet was in fact successfully received. If no acknowledgment packet is received back from the receiver at the transmitter, the transmitter eventually will resend the packet after a predetermined interval of time has elapsed. In unacknowledged connection mode, it is up to the application program to determine that it has not received a data packet and to request retransmission of that packet.
While FIG. 1 depicts the original topology for which Ethernet was designed, the Ethernet 802.3 protocol is employed in a variety of network topologies. FIG. 2 shows a well known modification to the bus topology, which is use of a bridge 36 to link one bus to a second bus. In a bridged system the separate buses are referred to as "segments." A bridge is a computer having a processor, a memory for storing network information, connections to two or more separate communication channel segments such as 32 and 34, a separate bridge adaptor for handling transmissions on each segment, and a buffer memory for storing packets received from one channel for transmission on another channel. Bridge 36 receives packets from a source segment such as channel 32, stores the packets, and then transmits the packets on another segment such as 34, when the bridge detects that the other channel is silent.
In a bridged 802.3 network, stations transmitting packets transmit as though all the stations were on the same bus segment. In other words, at the Media-access Control level, the stations transmit a packet with a destination address with no knowledge whether the packet's destination can receive the packet directly or whether the packet will be bridged. A typical prior-art bridge, therefore, must examine every packet on every segment to which it is connected to determine whether that packet must be bridged to a different segment. Prior art bridges typically will temporally store every packet transmitted on each segment in a receive buffer and then examine the destination address of the buffered packet. If the destination address is for a station on the same segment as the originating station, then the packet has presumable already been received by the destination station and the bridge discards or "filters" the buffered packet. If the destination address is for a station on a different segment from the originating station, the bridge "bridges" the packet by transmitting it on the destination station's bus.
FIG. 3 shows another network topology well known in the art and that may be employed in an 802.3 Ethernet, a star topology. As shown in FIG. 3, a star topology is characterized by a hub 42. A hub provides functions similar to a bridge, but with connections to more than two separate communication channels. In a hub, these connections are sometimes referred to as "ports." Each connection is controlled by a separate hub adaptor. The hub may include a number of point-to-point CSMA/CD connections where just one station is connected to a communications channel, such as 12a', 12b', and 12c', and may also include one or more connections to a segment 14 containing multiple stations, such as 12a-d. On the point-to-point connections, all packet traffic to and from stations 12a'-c' is routed through hub 42. Hub 42 receives and buffers packets from the stations, examines the packets to determine the destination address of those packets, looks up the packet addresses in a link-table that contains routing information for each destination address (typically this routing information specifies which hub port the packet should be transmitted out on), and then transmits the packets out over the appropriate port for that destination.
In a multi-port hub, packets may be coming in at a number of ports, all destined for just one out-going port. Hubs typically include some type of packet storage memory so that incoming packets may be temporarily stored while waiting for an outgoing port to become available. However, typical prior art hubs have no means of flow control so once the incoming receive data storage for a port has been filled up, any new packets received at that port are simply dropped or discarded by the hub. These prior art hubs rely on this dropped packet being detected in either the source or destination station by upper layer software protocols. These software protocols expect to see an explicit/implicit acknowledge for every packet from the destination. (Protocols that have burst modes allow one acknowledge packet to implicitly confirm that a group of packets have successfully been received.) The source node has a timer that it uses to wait for an acknowledge pack from the destination. If this timer expires the source re-transmits the packet. This timer is generally in the order of seconds. Therefore, in prior art hubs, a dropped packet will take several seconds to be detected and retransmitted. Dropped packets are also expensive in terms of consuming network resources because both the transmitting station and the hub must perform all the operations necessary to transfer a full packet before the decision is made to discard the packet.
One prior art system partially recognized this problem in regards to a standard bridge as shown in FIG. 2. Published Japanese Patent Application 1-222373 to Sakamoto, describes having a bridge adaptor jam packets when its receive buffers are full in order to avoid discarding the packets in the bridge after reception. However, the jamming method discussed cannot detect when a destination port is busy or occupied and therefore does not prevent many dropped packets. The method discussed provides inferior performance because it only starts jamming when the receive buffer is completely full. Thus, the method tries to act as an on/off switch. However, this presents a problem when combined with the 802.3 CSMA/CD standard because once a source node has tried to transmit a packet 16 time and has experienced a collision or jam each time, the source adaptor simply discards the packet. When these packets are dropped due to excessive collisions, the source node logs this error on the source node even though the source node was not the cause of the packet being rejected. Existing network management packages therefore may have problems isolating the cause of the problem and so the method is not transparent to the network.
What is needed is a CSMA/CD networking system that can handle the problem of some packet destinations not being always available to receive packets without incurring the network overhead costs associated with dropping a packet at the hub.